//平衡二叉搜索树（AVL树）
#ifndef __AVLTREE__HPP
#define __AVLTREE__HPP

#include"BinarySearchTree.hpp"

namespace NgSiuKei {

//构建
template<class TheClass>
binary_tree_node<TheClass> *createAVLTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return nullptr;
    }

    //获取排序后的参数
    U_L_L nodeNum = getTreeNodeNum(tree);
    TheClass *array = orderTree(tree, ORDER_TYPE_PRE);
    bubbleSort(array, nodeNum);

    return createAVLTreeWithVals(array, (nodeNum-1)/2);
}

template<class TheClass>
static binary_tree_node<TheClass> *createAVLTreeWithVals(TheClass *vals, U_L_L len, U_L_L index) {
    if(-1 == index) {
        return nullptr;
    }
    binary_tree_node<TheClass> *tree = new binary_tree_node<TheClass>;
    tree->val = vals[index];
    tree->leftChild = createAVLTreeWithVals(vals, len, index/2);
    tree->rightChild = createAVLTreeWithVals(vals, len, (index+len)/2);
    return tree;
}

//二叉搜索树->AVL树
template<class TheClass>
void convertToAVLTree(binary_tree_node<TheClass> *&tree) {
    if(nullptr == tree || !isBST(tree) || isAVLTree(tree)) {
        return;
    }

    //先将子树变为AVL树再转换自己
    convertToAVLTree(tree->leftChild);
    convertToAVLTree(tree->rightChild);
    
    //不平衡的四种情况：LL、RR、LR、RL
    const int L = 1, R = 2, LL = 11, RR = 22, LR = 12, RL = 21;

    //现在要找出是哪个情况
    int type = 0;//记录是哪个情况
    binary_tree_node<TheClass> *higherChild = nullptr;//记录高的那颗子树
    U_L_L leftTreeHeight = getTreeHeight(tree->leftChild);
    U_L_L rightTreeHeight = getTreeHeight(tree->rightChild);
    if(leftTreeHeight < rightTreeHeight) {
        type = R;
        higherChild = tree->rightChild;
    }
    else {
        type = L;
        higherChild = tree->leftChild;
    }

    //记录高子树的左右子子树高度，通过比较子子树高度告诉计算出最终的失衡情况
    leftTreeHeight = getTreeHeight(higherChild->leftChild);
    rightTreeHeight = getTreeHeight(higherChild->rightChild);
    if(leftTreeHeight == rightTreeHeight) {
        //这里很难解释，自己画图模拟一下转换过程，看看规律就知道了
        type = (type * 10) + type;
    }
    else if(leftTreeHeight < rightTreeHeight) {
        type = (type * 10) + R;
    }
    else {
        type = (type * 10) + L;
    }

    //根据不同情况做不同旋转处理，进而成为AVL树
    switch(type) {
        case LL: {
            rightRotation(tree);
            break;
        }
        case RR: {
            leftRotation(tree);
            break;
        }
        case LR: {
            leftRotation(tree->leftChild);
            rightRotation(tree);
            break;
        }
        case RL: {
            rightRotation(tree->rightChild);
            leftRotation(tree);
            break;
        }
        default: {
            break;
        }
    }

    if(!isAVLTree(tree)) {
        convertToAVLTree(tree);
    }
}

//判断是不是AVL树
template<class TheClass>
bool isAVLTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return true;
    }
    if(!isBST(tree)) {
        return false;
    }
    U_L_L leftHeight = getTreeHeight(tree->leftChild);
    U_L_L rightHeight = getTreeHeight(tree->rightChild);
    if(leftHeight < rightHeight) {
        return (rightHeight-leftHeight)<2;
    }
    else if(leftHeight > rightHeight) {
        return (leftHeight-rightHeight)<2;
    }
    else {
        return true && isAVLTree(tree->leftChild) && isAVLTree(tree->rightChild);
    }
}

//插入数据
template<class TheClass>
void insertValToAVL(binary_tree_node<TheClass> *&tree, TheClass val) {
    insertValToBinarySearchTree(tree, val);
    if(!isAVLTree(tree)) {
        convertToAVLTree(tree);
    }
}

//删除数据
template<class TheClass>
void deleteValToAVL(binary_tree_node<TheClass> *&tree, TheClass val) {
    deleteValFromBinarySearchTree(tree, val);
    if(!isAVLTree(tree)) {
        convertToAVLTree(tree);
    }
}

}

#endif